/*
Date:20211006
key:返回的索引而不是数字有助于递归终止的判断
*/
class Solution {
public:
    int FindK(vector<int>& nums,int st,int en)
    {
        if(st>en){return -1;}
        int i=st,j=en;
        int key=nums[st];
        while(i<j)
        {
            while(key<=nums[j]&&i<j)
            {
                j--;
            }
            while(key>=nums[i]&&i<j)
            {
                i++;
            }
            if(i<j){swap(nums[i],nums[j]);}
        }
        swap(nums[st],nums[i]);
        if(i==nums.size()-3){return i;}
        else
        {
            int a=FindK(nums,st,i-1);
            if(a>0)
            {
                return a;
            }
            int b=FindK(nums,i+1,en);
            if(b>0)
            {
                return b;
            }
            return -1;
        }
    }
    int thirdMax(vector<int>& nums) {
    set<int>s(nums.begin(),nums.end());
    vector<int>re;
    for(int tmp:s)
    {
        re.push_back(tmp);
    }
    if(re.size()<3)
    {
        return *max_element(re.begin(),re.end());
    }
    else
    {   

        return re[FindK(re,0,re.size()-1)];
    }
    return 0;

    }
};